package com.leetcode.algorithms.one.problem2;

import java.math.BigInteger;

/**
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807
 */
public class AddTwoNumByListNode {
	public static ListNode createListNode(int num){
		return createListNode(new BigInteger(num+""));
	}
	
	public static ListNode addTwoNumbers(ListNode l1,ListNode l2){
//		return bigInteger2Node(listNode2Decimal(l1).add(listNode2Decimal(l2)));
		//创建虚拟头
		ListNode dummyHead = new ListNode(0);
		//当前curr指向虚拟头对象
	    ListNode p = l1, q = l2, curr = dummyHead;
	    int carry = 0;
	    while (p != null || q != null) {
	        int x = (p != null) ? p.val : 0;
	        int y = (q != null) ? q.val : 0;
	        int sum = carry + x + y;
	        carry = sum / 10;
	        //把当前位相加的结果设置到curr的next节点   -->第一次执行实质上同时把dummyHead的next节点设置了
	        curr.next = new ListNode(sum % 10);
	        //把curr节点指向curr节点的next   实质上curr指向的一直是dummyHead的末位非null节点
            //基于以上实现了每次相加的结果保存到对应的位置
	        curr = curr.next;
	        if (p != null) p = p.next;
	        if (q != null) q = q.next;
	    }
	    if (carry > 0) {
	        curr.next = new ListNode(carry);
	    }
	    return dummyHead.next;
	}
	
	public static ListNode addTwoNumbers1(ListNode l1,ListNode l2){
//		return bigInteger2Node(listNode2Decimal(l1).add(listNode2Decimal(l2)));
	    ListNode p = l1, q = l2;
	    int sum=p.val+q.val;
	    ListNode result = new ListNode(sum%10);
	    ListNode curr = result;
	    int carry = sum/10;
	    p=p.next;q=q.next;
	    
	    while(p != null && q != null){
	    	sum = carry + p.val + q.val;
	        carry = sum / 10;
	        curr.next = new ListNode(sum%10);
	        curr =curr.next;
	        p = p.next;
	        q = q.next;
	    }
	    if(carry==0){
	    	curr.next=p==null?q:p;
	    }else{
	    	p=p==null?q:p;
	    	while(p!=null){
		    	sum = carry + p.val;
		    	carry = sum / 10;
		        curr.next = new ListNode(sum%10);
		        curr =curr.next;
		        p=p.next;
		    }
	    	if (carry > 0) {
		    	curr.next = new ListNode(carry);
		    }
	    }
	    
	    return result;
	}
	
	
	
	static ListNode bigInteger2Node(BigInteger num){
		if(num.compareTo(BigInteger.TEN)>=0){
			ListNode node = new ListNode(num.remainder(BigInteger.TEN).intValue());
			node.next=bigInteger2Node(num.divide(BigInteger.TEN));
			return node;
		}
		return new ListNode(num.intValue());
	}
	
	public static ListNode createListNode(BigInteger num){
		String string = num.toString();
		int len = string.length();
		ListNode node =null;
		ListNode next =null;
		for(int i=0;i<len;i++){
			node= new ListNode(string.charAt(i)-48);
			node.next = next;
			next = node;
		}
		return node;
	}
	
	public static BigInteger listNode2Decimal(ListNode node){
		StringBuilder sb = new StringBuilder(node.val+"");
		ListNode next = node.next;
		while(next!=null){
			sb.insert(0, next.val);
			next = next.next;
		}
		return new BigInteger(sb.toString());
	}
	
	
	
	public static void main(String[] args) {
//		char c ='0';
//		System.out.println(c-48);
//		createListNode(123);
		//1-5-3
        //2-8-6-2
		
		System.out.println(addTwoNumbers(createListNode(351), createListNode(2682)));
	}
}
